Data deduplication is used in various computing environments, such as virtualized and non-virtualized computing environments, to minimize repeated data. For example, in a virtualized computing environment, more than one virtual machine can be provisioned on a host machine resulting in a high degree of repeated data. As another example, in a physical computer system (e.g., non-virtualized environment), many blocks of data from the computer systems operating system, user files, etc. can include repeated data. In order to deduplicate underlying file system data, within the different computing environments, deduplication metadata is generated that describes the relationship between the actual data stored on disk, or in memory, and the data files, application, etc. within the file system. In the event of an unclean shutdown, such as a shutdown due to a system failure, loss of power, improper shutdown procedure, emergency, etc., the deduplication metadata should be brought in line with the file system data. During this process, which can be referred to as file system recovery, user access to the underlying file system data is delayed until the file system recovery is completed. This duration of the delay is proportional to the used storage space of the file system, which for large scale systems, can take many minutes. Such a delay is often unacceptable to users, especially for users of high availability systems.